/*
 * list.cpp
 *
 *  Created on: 25 Nov 2010
 *      Author: samuel
 */
#include "../include/list.h"
#include "stdio.h"
#include "stdlib.h"
#include "assert.h"


struct Node
{
    ElementType data;
    PtrToNode next;
};


static Position FindPrevious(const List l, ElementType x);


static Position FindPrevious(const List l, ElementType x)
{
    assert(l != 0);

    PtrToNode p = l;
    while (p->next != 0 && p->next->data != x)
    {
        p = p->next;
    }

    return p->next == 0 ? 0 : p;
}

void Insert(ElementType data, List l, Position p)
{
    assert(l != 0 && p != 0);

    PtrToNode q = (PtrToNode)malloc(sizeof(struct Node));
    if (q != 0)
    {
        q->data = data;
        q->next = p->next;
        p->next = q;
    }
}

List MakeList(const ElementType data[], int size)
{
    assert(data != 0 && size > 0);

    List l = (List)malloc(sizeof(struct Node));
    if (l != 0)
    {
        l->next = 0;

        for (int i = 0; i < size; i++)
        {
            Insert(data[i], l, l);
        }
    }

    return l;
}

List SortList(List l)
{
	assert (l != 0);

	Node value;
	PtrToNode tail = &value;

	while (l->next)
	{
		PtrToNode pre, min, p;
		for (pre = l, min = p = l->next; p->next; p = p->next)
		{
			if (p->next->data < min->data)
			{
				pre = p;
				min = p->next;
			}
		}

		pre->next = min->next;		//remove min

		tail->next = min;			//append min to value
		tail = min;
	}

	l->next = value.next;

	return l;
}

void PrintList(const List l)
{
    assert(l != 0);

    PtrToNode p = l->next;

    while (p != 0)
    {
        printf("data: %d\n", p->data);
        p = p->next;
    }
}

int IsEmpty(const List l)
{
    assert(l != 0);

    return l->next == 0;
}

Position Find(const List l, ElementType x)
{
    assert (l != 0);

    PtrToNode p = l->next;
    while (p != 0 && p->data != x)
    {
        p = p->next;
    }

    return p;
}

void Delete(List l, ElementType x)
{
    assert(l != 0);

    PtrToNode p = FindPrevious(l, x);
    if (p != 0)
    {
        PtrToNode q = p->next;
        p->next = q->next;
        free(q);
    }
}
